The present invention relates generally to the field of packet communication, and, more particularly, to using a packet frame-check sequence (FCS) to convey information.
A common error detection technique that may be used in packet communication networks is known cyclic redundancy check (CRC). This technique may be explained as follows: Given a k-bit frame or message, a transmitter generates an n-bit sequence, known as a frame-check sequence (FCS), so that the resulting packet, consisting of k+n, bits is exactly divisible by some predetermined number. A receiver then divides the incoming packet by the same number and, if there is no remainder, assumes that there was no error.
Principles of the basic CRC algorithm may be expressed mathematically as follows: Let I(x) by a polynomial representing the message to be transmitted and let G(x) be a generating polynomial of degree n for the CRC algorithm. Typically, I(x) is multiplied by xn to left shift the message to make room for the n-bit FCS, which is denoted by R(x), at the low order of the packet. The relationship between I(x), G(x), and R(x) may expressed as set forth in Equation 1:
(xn)I(x)=Q(x)G(x)+R(x),xe2x80x83xe2x80x83EQ. 1
where Q(x) is the quotient that results from dividing (xn)I(x) by G(x). The product Q(x)G(x) may be added to both sides of Equation 1, which yields Equation 2 below:
xe2x80x83R(x)=(xn)I(x)+Q(x)G(x).xe2x80x83xe2x80x83EQ. 2
Note that Q(x)G(x)+Q(x)G(x) equals zero as any binary number added to itself is zero for the case of finite field coefficients. Equation 2, however, may be rewritten as a statement of congruence as set forth in Equation 3:
R(x)=(xn)I(x) mod G(x).xe2x80x83xe2x80x83EQ. 3
Thus, the FCS R(x) is given by the remainder that results from the division of the left shifted message polynomial (xn)I(x) by the generator polynomial G(x).
Conventional packet communication systems have used the FCS to convey information, such as an address or xe2x80x9ccolor code.xe2x80x9d A color code may be a code used to identify packets that are intended for multiple receiving stations. In this regard, a first group of receiving stations may accept packets encoded using a first color code, a second group of receiving stations may accept packets encoded using a second color code, etc. A transmitting station may append an address or color code to the high-order end of a message to create an extended message. The CRC algorithm may then be used to compute the FCS for the extended message. The FCS may be appended to the low-order end of the extended message to prepare the extended message for transmission. Before transmitting the extended message, however, the address or color code is removed from the high-order end of the extended message leaving the original message and the FCS computed for the extended message. A packet comprising the original message the FCS computed for the extended message may then be transmitted to one or more receiving stations.
Upon receipt of the packet at a receiving station, the receiving station may append its own address or accepted color code at the high-order end of the packet. The receiving station may then use the CRC algorithm to determine if the packet is in congruence with the CRC generator polynomial. If the packet is in congruence with the CRC generator polynomial, then the receiving station may presume that the transmitting station has addressed or color coded the packet for it. On the other hand, if the packet is not in congruence with the CRC generator polynomial, then the receiving station may presume that the transmitting station has addressed or color coded the packet for another receiving station or that the packet has been corrupted with a channel error. In this case, the packet may be discarded. Alternatively, conventional receiving stations may compute the FCS for the packet after appending their own address or accepted color code at the high-order end of the packet. If the computed FCS matches the FCS transmitted with the packet, then a receiving station may accept the packet, otherwise, the receiving station may discard the packet. In this manner, a packet may carry address or color code information for the packet implicitly in the FCS without increasing the size of the message field or adding one or more new information fields to the packet.
According to embodiments of the present invention, methods, communication devices, communication systems, and computer program products may be provided for communicating information via a frame-check sequence having an information block associated therewith. For example, one or more information blocks may be provided and respectively associated with one or more information block frame-check sequences. A message for transmission may be provided and a message frame-check sequence may be computed based on the message. One of the information blocks may also be selected for transmission along with the message. Rather than constructing a packet that includes both the selected information block and the message, however, the information block frame-check sequence that is associated with the selected information block is added to the message frame-check sequence to compute a transmit frame-check sequence. A packet comprising the message and the transmit frame-check sequence may then be transmitted.
In accordance with further embodiments of the present invention, the associations between the one or more information blocks and the one or more information block frame-check sequences are also provided at a receiver where the packet is received. Once received, the packet may be divided by a generator polynomial to determine whether any remainder results. If the remainder is non-zero, then a determination may be made whether remainder corresponds to any of the one or more information block frame-check sequences. If the remainder does correspond to one of the information block frame-check sequences, then the information block associated with the information block frame-check sequence that corresponds to the remainder may be processed as received information.
The present invention takes advantage of the principles of linearity and superposition inherent in the basic cyclic redundancy check (CRC) algorithm. Advantageously, the frame-check sequence for an information block may be added to the frame-check sequence for a message to thereby encode the information block into the packet. When the packet is received, a CRC operation may be performed, which results in a remainder corresponding to the frame check sequence for the encoded information block. Associations may be developed a priori between the one or more information blocks and their frame check sequences. Moreover, these associations may be stored, for example, in a data structure, such as a table. The remainder may thus be used to index the table and recover the encoded information block.
In accordance with further embodiments of the present invention, if dividing a received packet by the generator polynomial does not result in any remainder, then the receiver may presume that an information block has not been encoded in the packet and, therefore, only the message is processed as received information. Thus, broadcast packets (i.e., packets that are not specifically addressed or color coded) may be received and processed after performing a single CRC operation.
The present invention may decode packets from an information stream that includes both broadcast packets and packets that are addressed or color coded for specific receivers without performing multiple CRC analysis operations. That is, as discussed hereinabove, if dividing a received packet by the generator polynomial results in a non-zero remainder, then that remainder may be used, for example, to index a data structure in which information blocks are associated with frame check sequences. By determining which, if any, of the one or more information block frame check sequences corresponds to the remainder, the associated information block may be recovered from the data structure and processed as received information without the need to append a prospective information block to the received packet and perform an additional CRC analysis.
In accordance with still further embodiments of the present invention, a received packet may be discarded if dividing the received packet by the generator polynomial results in a remainder, but the remainder does not correspond to any of the one or more information block frame check sequences. In this case, a receiver may presume that the received packet has been corrupted with a communication channel error.
In accordance with other embodiments of the present invention, each of the one or more information blocks may be represented by a K-bit field where K greater than 0. Moreover, each of the one or more information blocks may be associated with their respective information block frame check sequences by determining, for each bit position in the K-bit field, if any of the one or more information blocks contain a nonzero bit in that specific bit position. If at least one of the one or more information blocks contains a non-zero bit in a specific one of the K bit positions, then a bit position frame check sequence may be computed for that specific bit position (i.e., a one in that specific bit position and zeros in the other Kxe2x88x921 bit positions).
In accordance with still other embodiments of the present invention, the information block frame check sequence corresponding to the selected information block may be constructed by selecting the bit position frame check sequences corresponding to non-zero bit positions in the selected information block and then adding these selected bit position frame check sequences together to compute the information block frame check sequence. By exploiting the linearity and superposition principles of the basic CRC algorithm, the present invention may use a data structure with at most K bit position frame check sequences stored therein to compute the information block frame check sequences. This data structure may consume substantially less memory than the memory that may otherwise be needed to store an information block frame check sequence for every possible information block.
Although the present invention has been described above primarily with respect to method aspects of the invention, it will be understood that the present invention may be embodied as methods, communication devices, communication systems, and computer program products.